COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00006 00003	%this has been added to a15.tex Cartesian Products and Ordered Pairs.
C00011 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a57.tex[154,phy] \today\hfill}

\parskip 5pt
\bigskip
\line{\bf Closures\hfill}

(Assumes Tarski-Knaster.)

A relation $\tau$ is reflexive if $\tau\supseteq \iota$; symmetric if
$\tau\supseteq\hat{\tau}$; transitive if $\tau\supseteq\tau↑2$; and an
equivalence relation if $\tau\supseteq\iota\cup\hat{\tau}\cup\tau↑2$. All
these requirements are of the form $\tau\supseteq f(\tau)$, where $f$
is monotone. For any relation~$\rho$, the Tarski-Knaster theorem
provides an LFP/LC of $x\supseteq \rho\cup f(x)$; that relation is the
unique least relation~$\tau$ that contains $\rho$ and has the property
expressed by $\tau\supseteq f(\tau)$. Such relations are called {\it closures\/}
of~$\rho$.

The {\it reflexive closure\/} of $\rho$ is the LC of $x\subseteq \rho\cup\iota$,
namely $\rho\cup\iota$ itself. It is the least relation that contains~$\rho$
and is reflexive.

The {\it transitive closure\/} of $\rho$, called $\rho↑+$, is the LC of
$x\supseteq \rho\cup x↑2$, and also of $x\supseteq\rho\cup x\cdot\rho$.
It is the least transitive relation that contains~$\rho$;
$\rho↑+=\bigcup↓{i≥1}\rho↑i$. ({\bf Drill}: prove~it.)

The {\it reflexive transitive closure\/} of $\rho$, called $\rho↑{\ast}$, is
the LC of $x\supseteq\rho\cup\iota\cup x↑2$, and also of $x\supseteq\iota\cup
x\cdot\rho$. It is the least reflexive transitive relation that contains~$\rho$;
$\rho↑{\ast}=\bigcup↓{i≥0}\rho↑i$. ({\bf Drill}:  prove~it.)

The {\it equivalence closure\/} of $\rho$ does not have a conventional notation;
we shall call it $\rho↑{\equiv}$. It is the LC of $x\supseteq\rho\cup\iota\cup
\hat{x}\cup x↑2$, also of $x\supseteq\iota\cup x\rho\cup x\hat{\rho}$.
It is the least equivalence relation that contains~$\rho$; $\rho↑{\equiv}=
(\rho\cup\hat{\rho})↑{\ast}$.

\medskip
({\it Exercise\/}; prove directly, without citing the Tarski-Knaster theorem,
that the intersection of all transitive relations which include~$\rho$
is itself a transitive relation which includes~$\rho$.)


\vfill\eject

%this has been added to a15.tex Cartesian Products and Ordered Pairs.
\line{\sevenrm OLD a57.tex[154,phy] \hfill}

\bigskip
\line{\bf Transitive Closures\hfill}

Let $R$ be a relation on~$S$. Define $R↑+$ as the intersection of all
relations~$T$ that both include~$R$ and are transitive. There is at least
one such relation, namely $T=S\times S$, so the intersection exists.
Because $R↑+$ is the intersection of relations all of which include~$R$,
$R\subset R↑+$. If $R↑+$ were not transitive, there would be $i$, $j$,
and~$k$ in~$S$ for which $iR↑+j$, $jR↑+k$, but not $iR↑+k$. Then there
must be some~$T$ for which $\neg iTk$, but $R↑+\subseteq T$, so $iTj$,
$jTk$, contradicting the transitivity of~$T$.

We want to show that $R↑+$ is the uniquely smallest addition to~$R$
(i.e., relation that includes~$R$) that is transitive. If $T$ is any
other, $T$~appears in the intersection that gives~$R↑+$, so $R↑+\subset T$,
and $T$~is not the smallest. We call $R↑+$ the {\sl transitive closure\/}
of~$R$.

The pattern of the above proof occurs repeatedly in mathematics; if you want
the smallest set with a certain property, and you suspect that there is
one set that is included in all the others having that property, try
taking the intersection of all the sets with property~$P$, and see if you
can prove it has the property. If you want the largest set that has a
certain property, take the union of all that have the property.

For example, if I want the smallest set that includes 6 and 15, and is
closed under subtraction, I~try the intersection of all such sets. One
such set is the set of multiples of three, so the intersection will only
contain multiples of three. All such sets contain $9=15-6$, and
$3=9-6$. If such a set contains~3, it contains $0=3-3$, $-3=0-3$,
$6=3-(-3)$, $9=6-(-3)$, etc., so the intersection contains all the
multiples of three. The intersection then is exactly the set of multiples
of three, and one more step ({\bf Drill:} What remains to prove?)
shows the intersection is what we were looking for.

If we want the smallest relation $R↑\ast$ that includes~$R$, and is
reflexive as well as transitive, we again try the intersection of all
such relations. 

{\bf Drill:} Show that the intersection has the required properties.

{\bf Drill:} What is the smallest equivalence relation that includes~$R$?

{\bf Drill:} Show by induction that $R↑i\subset R↑{\ast}$ for all $i≥0$.

{\bf Drill:} Show $\cup↓{i≥0}R↑i=R↑{\ast}$.
({\bf Answer:} From previous drill, $\cup↓{i≥0}R↑i\subset R↑{\ast}$. Because
$\cup↓{i≥0}R↑i$ is reflexive, transitive, and contains~$R$,
$R↑{\ast}\subset\cup↓{i≥0}R↑i$. So $R↑{\ast}=\cup↓{i≥0}R↑i$.)


\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
September 5, 1986.
%revised date;
%subsequently revised.

\bye